// 2025/11/9
// 最长连续序列


// 排序 + 遍历 效率较高
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), count = 1, ans = 0;
        for(int i = 1; i <= n; i++)
        {
            if(i != n && nums[i] == nums[i - 1])
                continue;
            if(i == n || nums[i] != nums[i - 1] + 1)
            {
                ans = max(ans, count);
                count = 0;
            }
            count++;
        }
        return ans;
    }
};

// 哈希
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set(nums.begin(), nums.end());
        int ans = 0;
        for(auto num : num_set)
        {
            if(!num_set.count(num - 1))
            {
                int cur = 1;
                while(num_set.count(num + 1))
                {
                    num++, cur++;
                }
                ans = max(ans, cur);
            }
        }
        return ans;
    }
};